package dfs_bfs;

public class lc1254 {
    public static void main(String[] args) {
        System.out.println(closedIsland(new int[][]{{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},
                {1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0,1},{1,1,1,1,1,1,1,0}}));
    }
    public static int closedIsland(int[][] grid) {
        int m = grid.length, s = 0;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, grid[0].length - 1);
        }
        for (int i = 0; i < grid[0].length; i++) {
            dfs(grid, 0, i);
            dfs(grid, grid.length - 1, i);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 0){
                    s += 1;
                    dfs(grid, i, j);
                }

            }
        }
        return s;
    }
    public static void dfs(int[][] grid, int i, int j){
        if(i >= grid.length || i < 0 || j < 0 || j >= grid[0].length || grid[i][j] == 1)
            return;
        grid[i][j] = 1;
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}
